package main

import (
	"fmt"
	"sort"
)

/**
执行用时：28 ms, 在所有 Go 提交中击败了11.71%的用户
内存消耗：6.8 MB, 在所有 Go 提交中击败了5.09%的用户
 */
func threeSumClosest(nums []int, target int) int {

	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})

	res := []int{INT_MAX, INT_MIN}
	for i := 0; i < len(nums); i++ {
		for j, k := i + 1, len(nums) - 1; j < k; j++ {
			for j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target { k-- }
			s := nums[i] + nums[j] + nums[k]
			res = min(res, []int{abs(s - target), s})
			if j < k - 1 {
				s = nums[i] + nums[j] + nums[k - 1]
				res = min(res, []int{abs(s - target), s})
			}
		}
	}
	return res[1]
}

// 求绝对值
func abs(a int) int {
	if a < 0 { a = -a }
	return a
}

// 两个数组较小的一个
func min(a []int, b []int) []int {
	for i := 0; i < len(a) || i < len(b); i++ {
		if i >= len(a) { return a }
		if i >= len(b) { return b }
		if a[i] < b[i] {
			return a
		} else if a[i] > b[i] {
			return b
		}
	}
	return a  // 说明 a == b, 随便返回一个即可
}

const INT_MAX = (1 << 31) - 1
const INT_MIN = -(1 << 31)

func main() {

	nums := []int{-1, 2, 1, -4}
	fmt.Println(threeSumClosest(nums, 1))
}
